Computer systems commonly have a plurality of components, such as processors, memory, and input/output devices, and a shared bus for transferring information among two or more of the components. The components commonly are coupled to the bus in the form of component modules, each of which may contain one or more processors, memory, and/or input/output devices. Information is transmitted on the bus among component modules during bus "cycles," each bus cycle being a period of time during which a module has control of the bus and is permitted to transfer, or drive, a limited quantity of information on the bus. Modules communicate by sending each other "transactions" on the bus that take one or more cycles to complete, such as conventional "read" and "write" transactions.
Typically, only one module can send, or drive, information on a shared bus in a given cycle. Thus, any shared bus system must have a bus "arbitration" scheme for determining which module is entitled to drive information on the bus in a particular cycle. Many conventional bus arbitration schemes are available. In most arbitration schemes, each module in a shared bus system generates a signal when it wants to drive the bus, and an arbitration algorithm implemented on one or more processors determines which module is entitled to drive the bus during a given cycle.
Conventional arbitration schemes are generally designed to allow each module seeking to use the bus an opportunity to do so, so that each module is able to make forward progress on the transactions it needs to issue. For example, in a conventional round-robin arbitration scheme, the modules are effectively queued for arbitration priority purposes. The module at the head of the queue wins the bus during the next available bus cycle and is then placed at the end of the queue. Generally, this queuing of modules is implemented by defining an order for the modules and using a pointer that points to the module considered to be at the head of the queue. The module at the head of the queue will win arbitration for the next available cycle. After the module at the head of the queue wins arbitration, the pointer advances to next module according to the defined order. After each module has had an opportunity to control the bus, the pointer returns to the first module in the order. In this manner, each module is assured an opportunity to control the bus on a somewhat regular basis, allowing the module to make forward progress with respect to the transactions it needs to issue. Many conventional arbitration schemes are available that are more complex than a round-robin scheme. It is generally desirable, however, for any arbitration scheme to assure that each module seeking to use the bus has the opportunity to do so and is therefore able to make forward progress.
If a module were always able to issue a transaction when it wins the arbitration, forward progress would be assured for all modules. In some bus systems, however, modules may be prevented from effectively issuing certain types of transactions during certain cycles. For example, input/output transactions may be prohibited during certain cycles, or may be aborted after being issued when input/output modules are too busy to accept any new transactions. Similarly, if the memory controller for a computer system is too busy to accept any new transactions for processing, all new memory-related transactions may be prohibited or aborted until the memory controller can again accept new transactions. Transactions that are aborted, or prevented from being issued, are retained by the relevant module until the transactions can be effectively issued.
In bus systems where classes of transactions cannot be effectively issued during certain cycles, it is possible for a module to be delayed or prevented from making forward progress for undesirably long periods of time. For example, a module may arbitrate for control of the bus to write data to an input/output device, but obtain control of the bus during a cycle when input/output transactions cannot be effectively issued. The module ordinarily will then relinquish control of the bus and be given a lower priority with respect to other modules for a period of time (e.g., the module may be placed at the end of the queue in a round robin arbitration protocol). The module must then wait until it again wins arbitration before it can issue the transaction and make forward progress. While the module is at a lower priority, the transaction it seeks to issue may be temporarily permitted. However, by the time the module again wins control of the bus, the transaction it seeks to issue may again be prohibited. This may occur each time the module wins the bus for an undesirably long period of time. Thus, the module may be unable to make forward progress for undesirably long periods of time.
Accordingly, there is a need for an arbitration scheme that permits each module to make forward progress even though certain classes of transactions cannot be issued on the bus during one or more bus cycles.